%% if you are submitting an initial manuscript then you should have submission as an option here %% if you are submitting a revised manuscript then you should have revision as an option here %% otherwise options taken by the article class will be accepted \documentclass[revision]{FPSAC2026} %% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc %% note that the class file already loads {amsmath, amsthm, amssymb} \newtheorem{theorem}{Theorem} \newtheorem{lem}[theorem]{Lemma} \newtheorem{prop}[theorem]{Proposition} \newtheorem{cor}[theorem]{Corollary} \newtheorem{conj}[theorem]{Conjecture} \newtheorem{defn}[theorem]{Definition} \newtheorem{ex}[theorem]{Example} \newtheorem{rmk}[theorem]{Remark} \numberwithin{theorem}{section} \theoremstyle{definition} \numberwithin{equation}{section} \DeclareMathOperator{\sgn}{sgn} \DeclareMathOperator{\Comp}{Comp} \DeclareMathOperator{\SSYT}{SSYT} \newcommand{\MP}{\mathcal{M}\mathcal{P}} %\usepackage{ytableau} \usepackage[boxsize=15pt]{ytableau} \newcommand{\BA}[1]{\textcolor{cyan}{\sf BA: [#1]}} \newcommand{\rosa}[1]{{\color{red} \sf rosa: [#1]}} \newcommand{\mike}[1]{{\color{purple} \sf MZ: [#1]}} %% define your title in the usual way \title[Transition matrices for character bases] {Transition matrices for character bases of the symmetric group} %% define your authors in the usual way %% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details %% for more than 3 names, use the Oxford comma: One Author, Two Author, Red Author, \and Blue Author \author[Castellano, Orellana, Zabrocki]{Beth Anne Castellano\addressmark{1}\thanks{\href{mailto:elizabeth.a.castellano.gr@dartmouth.edu}{elizabeth.a.castellano.gr@dartmouth.edu}. Partially supported by NSF Graduate Research Fellowship and NSF grant DMS--2153998.}, Rosa Orellana\addressmark{1}\thanks{\href{mailto:rosa.c.orellana@dartmouth.edu}{rosa.c.orellana@dartmouth.edu}. Partially supported by NSF grants DMS--2153998 and DMS--2452044.}, \and Mike Zabrocki\addressmark{2}\thanks{{\href{mailto:zabrocki@yorku.ca}{zabrocki@yorku.ca}. Partially supported by NSERC/CRSNG.} \\ This material is also based upon work supported by the NSF, while RO and MZ were in residence at the ICERM semester program ``Categorification and Computation in Algebraic Combinatorics'' in Fall 2025.}} %% then use \addressmark to match authors to institutions here \address{\addressmark{1}Department of Mathematics, Dartmouth College, Hanover, NH, USA \\ \addressmark{2}Department of Mathematics and Statistics, York University, Toronto, Ontario, Canada } %% put the date of submission here \received{\today} %% leave this blank until submitting a revised version %\revised{} %% put your English abstract here, or comment this out if you don't have one yet %% please don't use custom commands in your abstract / resume, as these will be displayed online %% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year) \abstract{We consider inhomogeneous bases of symmetric functions which evaluate to characters of the symmetric group and are closely related to long-standing open problems in combinatorial representation theory such as the Kronecker problem and the restriction problem. We describe combinatorial interpretations for the transition matrices between the basis that evaluates to induced trivial characters (or permutation characters) and other classical bases of symmetric functions. The transition coefficients are closely related to the M\"obius function of the multiset partition poset and are expressed in terms of multisets of Lyndon words.} %\BA{should we say quasi-Lyndon? although it's not defined yet}\rosa{I think it is okay as the only words that we are not Lyndon are squares of odd Lyndon words.}} %% put your French abstract here, or comment this out if you don't have one %\resume{\lipsum[2]} %% put your keywords here, or comment this out if you don't have them yet \keywords{symmetric functions, symmetric group characters, combinatorial interpretation, Lyndon words} %% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier %% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text %% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex %% but you can use bibtex if you want \usepackage[backend=bibtex]{biblatex} \addbibresource{refs.bib} %% note the \printbibliography command at the end of the file which goes with these biblatex commands \articlenumber{39} \begin{document} \maketitle %% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above \section{Introduction} Let $\Lambda$ denote the ring of symmetric functions in infinitely many commuting variables. Given two bases $\{a_\lambda\}$ and $\{b_\lambda\}$ of $\Lambda$, we let $M(a,b)$ be the transition matrix that allows us to express elements of the $a$ basis in terms of the $b$ basis. In particular, $M(a,b)_{\lambda,\mu}$ is equal to the coefficient of $b_\mu$ in $a_\lambda$. Combinatorial interpretations for the entries of the transition matrices between all pairs of classical bases of $\Lambda$ are known \cite[Chap. I, Sec. 6]{Mac}; most of these can be expressed in terms of the Kostka matrix. Combinatorial interpretations for many of these bases were given by Remmel and his coauthors \cite{ER89, ER1, KR06}, including a combinatorial description of the inverse Kostka matrix. It is well-known that there are powerful connections between $\Lambda$ and the representation theory of both $GL_n$ and $S_n$. For example, irreducible $GL_n$ characters are equal to evaluations of Schur polynomials at the eigenvalues of elements of $GL_n$. In \cite{OZSnChars}, the second and third authors defined two new inhomogeneous bases for $\Lambda$, the \emph{irreducible character basis} $\{\tilde{s}_\lambda\}$ and \emph{the permutation character basis} $\{\tilde{h}_\lambda\}$. Evaluations of elements of the $\tilde{s}$ basis at roots of unity (eigenvalues of permutation matrices) yield irreducible characters of $S_n$. Similarly, evaluations of elements of the $\tilde{h}$ basis at roots of unity yield the characters of trivial representations induced from a Young subgroup to $S_n$. Further properties and product formulae for these bases are developed in \cite{AssafSpeyer,MLee,OZProds,OZHopf,ryba}. The $\tilde{s}$ basis and $\tilde{h}$ basis have a relationship analogous to that of the $s$ basis and $h$ basis, in that they are also related by Kostka numbers. By definition in \cite{OZSnChars}, for $n \geq 2|\mu|$, \[\tilde{h}_\mu = \sum_{|\lambda| \leqslant |\mu|} K_{(n-|\lambda|, \lambda),(n-|\mu|,\mu)} \tilde{s}_\lambda,\] and conversely, $\tilde{s}_\lambda$ can be expressed in terms of $\tilde{h}_\mu$'s with inverse Kostka coefficients. The $\tilde{s}$ basis is closely related to two key open problems in combinatorial representation theory: the Kronecker problem and the restriction problem. The structure coefficients of the $\tilde{s}$ basis are the \emph{reduced Kronecker coefficients}, studied in \cite{BdVO15,BOR1,IP24,Mur38,OZSnChars} \[\tilde{s}_\lambda\tilde{s}_\mu = \sum_\nu \bar{g}_{\lambda, \mu}^\nu \tilde{s}_\nu ~.\] Moreover, $M(s,\tilde{s})_{\lambda,\mu}$ is equal to the \emph{restriction coefficient} $r_{\lambda,\mu}$, where $\text{Res}_{S_n}^{GL_n} \mathbb{W}^\lambda = \bigoplus_\mu (\mathbb{S}^\mu)^{\oplus r_{\lambda,\mu}}$ and $\mathbb{W}^\lambda$ is the irreducible polynomial representation of $GL_n$ indexed by $\lambda$ and $\mathbb{S}^{\mu}$ is the irreducible representation of $S_n$, see \cite{HSW21, MLee2, NPPS24,OZSnChars}. To better understand the $\tilde{s}$ basis and $\tilde{h}$ basis in hopes of tackling these big open problems, a key first step is finding combinatorial interpretations for expansions of these bases into the classical bases of $\Lambda$, and vice versa. It is shown in \cite{OZSnChars} that $M(h, \tilde{h})_{\lambda, \mu}$ is counted by multiset partitions and $M(h, \tilde{s})_{\lambda, \mu}$ is counted by certain multiset tableaux. An interpretation for $M(e, \tilde{s})_{\lambda, \mu}$ using set-valued tableaux is given in \cite{OZHopf}. In this paper, we add to these results by proving combinatorial interpretations for the coefficients in the expansions of the $\tilde{h}$ basis into the homogeneous, monomial, and Schur bases. Because the entries of $M(h, \tilde{h})$ enumerate multiset partitions, a special case of these transition coefficients are closely related to the problem of computing the M\"obius function for the integer partition lattice ordered by refinement \cite{Ziegler} (see \cite{Stanley} p. 386) and more generally the poset of multiset partitions \cite{BabsonHersh}. We found the connection between these lattices and the combinatorics of sets of Lyndon words appearing in these coefficients to be surprising. This extended abstract is organized as follows. In Section \ref{sec: ht to h} we present and outline the proof of our main theorem: a combinatorial interpretation for $M(\tilde{h},h)_{\lambda, \mu}$. %In Section \ref{subsec: ht to h defs}, definitions and the theorem statement are given, and in Section \ref{subsec: ht to h approach}, we describe our approach to this hefty proof. Section \ref{subsec: ht to h cases} gives an overview of the arguments and lemmas used in each of the four cases of the proof. In Section \ref{sec: other transition matrices}, we give several consequences of this theorem, including combinatorial interpretations for $M(\tilde{h},m)_{\lambda, \mu}$ (Section \ref{subsec: ht to m}) and $M(\tilde{h},s)_{\lambda, \mu}$ (Section \ref{subsec: ht to s}). In Section \ref{subsec: prods} we state combinatorial interpretations for the expansion of the multiplicative basis $\{ \tilde{h}_{\lambda_1}\tilde{h}_{\lambda_2}\cdots \tilde{h}_{\lambda_{\ell(\lambda)}}\}_\lambda$ into these same classical bases. \section{A change of basis from $\tilde{h}$ to the homogeneous functions }\label{sec: ht to h} \subsection{Definitions and theorem statement}\label{subsec: ht to h defs} Let a \emph{word}, $w=a_1 a_2 \dots a_n$, be a sequence of positive integers. The \emph{length} of the word, $|w|=n$, is the number of symbols in the sequence. We define $m_a(w)$ to be the number of times that $a$ occurs in $w$. The \emph{content vector} of $w$ is the vector $(m_1(w), m_2(w), \ldots)$. A word $w$ is \emph{Lyndon} if $|w|=1$ or $w$ is strictly lexicographically smaller than all of its cyclic shifts. A word $w$ is \emph{quasi-Lyndon} if it is Lyndon or if $w=uu$ where $u$ is Lyndon and $|u|$ is odd. To express the coefficient $M(\tilde{h},h)_{\lambda,\mu}$ we need to define triples $w_i^j :=(w,i,j)$, where $w$ is a quasi-Lyndon word and $i,j \in \mathbb{Z}_{>0}$. Here we interpret $j$ as the number of copies of the subscripted word $w_i$, which is the quasi-Lyndon word $w$ with subscript $i$. For any $w_i^j$ we define its \emph{weighted content}, $\alpha(w_i^j)$, as $j$ times the content vector of $w$: \[ \alpha(w_i^j) := (j\cdot m_1(w), j\cdot m_2(w), \ldots)~.\] For any finite set $S$ containing elements $w_i^j$, we define the \emph{weighted content} of $S$ as: \[ \alpha(S) = \sum_{w_i^j\in S}\alpha(w_i^j)~. \] Let $e(S) := \#\{ w_i^j\ \in S :\, |w| \text{ is even}\}$. Then we define the \emph{sign} of $S$ as $\sgn(S) := (-1)^{e(S)}$. Let $\lambda, \mu$ be two partitions of any sizes. Define $\mathcal{M}_{\lambda,\mu}$ to be the set containing all sets $S$ of elements $w_i^j$ such that $\lambda = \alpha(S)$ and $\mu = \text{sort}(j\, : \, w_i^j \in S)$, such that each $w$ appearing in a triple in $S$ satisfies the following: \begin{enumerate} \item If $|w|$ is odd, then $i=1$ and $w$ appears in at most one triple in $S$. \item If $|w|$ is even, then $\{i\, : \, w_i^j\in S\} = \{1, 2, \ldots, k\}$, where $k$ is the number of times that $w$ appears in a triple in $S$ (i.e., every subscript from $1$ to $k$ occurs exactly once). \end{enumerate} We can now state our main result: \begin{theorem}\label{htil to h} For partitions $\lambda, \mu$ such that $|\mu| \leqslant |\lambda|$, \[ M(\tilde{h}, h)_{\lambda, \mu} = \sum_{S \in \mathcal{M}_{\lambda,\mu}} \sgn(S). \] \end{theorem} \begin{ex}\label{ht to h example} To compute $M(\tilde{h},h)_{(5,3),(2,2,1)} = +2$, we sum the signs of the elements in $\mathcal{M}_{(5,3), (2,2,1)}$, which are as follows: \begin{align*} & S_1 = \{1_1^2, 12_1^2, 12_2^1\} \text{, }\sgn(S_1)= (-1)^2 \quad\quad S_2 = \{1_1^2, 12_1^1, 12_2^2\} \text{, }\sgn(S_2)= (-1)^2 \\ & S_3 = \{11_1^2,12_1^1,2_1^2\} \text{, }\sgn(S_3)= (-1)^2 \quad\quad S_4 = \{1_1^2,1112_1^1,2_1^2\} \text{, }\sgn(S_4)= (-1)^1 \end{align*} Notice that each $S_i$ has superscripts $2,2,1$, the parts of $\mu$. Moreover, the total numbers of $1$'s and $2$'s in the subscripted quasi-Lyndon words (with multiplicity) in each $S_i$ are $5$ and $3$, respectively. \end{ex} A {\em{multiset partition}} $\pi$ of content $M = \{\!\!\{ 1^{\alpha_1}, 2^{\alpha_2}, \dots, \ell(\alpha)^{\alpha_{\ell(\alpha)}} \}\!\!\}$ is a multiset of multisets whose disjoint union (with multiplicity) is equal to $M$. The type of the multiset partition $\pi$ is an integer partition $\gamma = (\gamma_1, \ldots, \gamma_{\ell(\gamma)})$ such that there are distinct multisets $A_1, A_2, \ldots, A_{\ell(\gamma)}$ with $\pi = \{\!\!\{ A_1^{\gamma_1}, A_2^{\gamma_2}, \ldots, A_{\ell(\gamma)}^{\gamma_{\ell(\gamma)}} \}\!\!\}$. The second and third authors show in \cite{OZSnChars} that $M(h, \tilde{h})_{\mu, \gamma}$ is equal to the number of multiset partitions of content $\{\!\!\{ 1^{\mu_1}, 2^{\mu_2}, \dots, \ell(\mu)^{\mu_{\ell(\mu)}} \}\!\!\}$ and type $\gamma$. We denote this set of multiset partitions by $\Pi_{\mu, \gamma}$. %In this context, $\pi \in \Pi_{\mu, \gamma}$ having type $\gamma$ means that $\gamma$ is the partition of $\ell(\pi)$ consisting of the multiplicities of the multisets that occur in $\pi$. For example, $M(h,\tilde{h})_{(4,2),(2,1)} = 4$ because the four elements of $\Pi_{(4,2),(2,1)}$ are: \begin{align*} &1, 1 \mid 1, 2 \mid 1, 2 \quad\quad 1, 1, 2, 2 \mid 1 \mid 1 \quad\quad 1, 1, 1, 1 \mid 2 \mid 2 \quad\quad 2, 2 \mid 1, 1 \mid 1, 1. \end{align*} \subsection{Proof approach}\label{subsec: ht to h approach} To prove Theorem \ref{htil to h}, we show that our proposed combinatorial formula for $M(\tilde{h}, h)_{\lambda, \mu}$ does in fact yield the inverse matrix of $M(h,\tilde{h})$. In other words, we show \begin{equation}\label{eqn: goal} \sum_{\mu} \left( \sum_{S \in \mathcal{M}_{\lambda, \mu}} \sgn(S) \right) M(h, \tilde{h})_{\mu, \gamma} = \delta_{\lambda, \gamma}. \end{equation} Since $M(h, \tilde{h})_{\mu, \gamma} = | \Pi_{\mu,\gamma}|$, we can rewrite Equation \ref{eqn: goal} as a sum over pairs $(S, \pi) \in \mathcal{M}_{\lambda, \mu} \times \Pi_{\mu, \gamma}$ for any $\mu$, summing the sign of the set $S$ in each pair: \begin{equation}\label{eqn: goal 2} \sum_{\mu} \sum_{(S,\pi) \in \mathcal{M}_{\lambda, \mu} \times \Pi_{\mu, \gamma}} \sgn(S) = \delta_{\lambda, \gamma}.\end{equation} We now interpret each pair in $\mathcal{M}_{\lambda, \mu} \times \Pi_{\mu, \gamma}$ as a single object. Notice that for $(S, \pi) \in \mathcal{M}_{\lambda, \mu} \times \Pi_{\mu, \gamma}$, the superscripts on the $w_i$'s in $S$ (which we can interpret as their multiplicities) are given by $\mu$, which also gives the content of the multiset partition $\pi$. Then within $\pi$, we can replace each occurrence of $k$ with a word $w_i$ such that $w_i^{\mu_k} \in S$. If multiple $w_i$'s in $S$ have the same superscript $\mu_k$, i.e., $\mu$ has multiple parts $\mu_k = \mu_{k+1} = \cdots =\mu_{k+m}$, then we assign the $w_i$'s to the values $k, \dots, k+m$ in increasing order, according to the following total order: $w_{i_1} < u_{i_2}$ if $w <_{\text{lex}} u$, or if $w = u$, then $i_1 |\gamma|$, we show that the signs of the elements of $\MP_{\lambda, \gamma}$ sum to $0$ by categorizing these elements into four cases. In some cases, cancellations are shown via sign-reversing involutions, while in others, the signs of entire subsets of $\MP_{\lambda, \gamma}$ are shown to sum to $0$. In every case, multiset partitions that are grouped together always have the same underlying content (number of $1$s, $2$s, etc.) per block. \subsection{Outline of cases}\label{subsec: ht to h cases} Throughout this section, when we say that $w$ with $|w|$ even is \emph{repeated} in $P \in \MP_{\lambda, \gamma}$ or a block of $P$, we mean that $w$ occurs multiple times with any possible subscripts in $P$ or a block of $P$. Note also that for $w$ with $|w|$ odd, every instance of $w$ in $P \in \MP_{\lambda, \gamma}$ has a subscript of 1, so we drop the subscripts on odd length words for simplicity. We organize the elements of $\MP_{\lambda, \gamma}$ into the following four cases. The descriptions of these cases do not partition $\MP_{\lambda, \gamma}$ into four disjoint subsets; rather, they are meant to be considered in an ``if, else'' structure, in the order in which they are presented (i.e. if $P \in \MP_{\lambda, \gamma}$ satisfies the conditions for Case 1, proceed there; else, consider whether $P$ satisfies the conditions for Case 2, and so on). Case 1 addresses elements that contain any non-Lyndon words or contain an odd length word that is repeated within a block. Case 2 handles elements that have an even length Lyndon word repeated (with any combination of subscripts) within a block. Case 3 tackles a subset of elements that have an even length Lyndon word that appears in more than one non-identical block (with any combination of subscripts). Finally, Case 4 addresses all remaining elements that did not fall into a previous case. \medskip \noindent{\bf Case 1: Non-Lyndon words and odd length words repeated within blocks.} This case is handled by a straightforward sign-reversing involution $\varphi$. If $P \in \MP_{\lambda, \gamma}$ contains a non-Lyndon word or has an odd length word repeated in a block, we choose $u$ to be the lexicographically smallest odd length Lyndon word such that either $uu$ appears in $P$ or $u$ is repeated in a block of $P$. If $u$ is repeated in at least one block of $P$, for every two copies of $u$ in a block, across all blocks, concatenate them into $uu$. If the largest subscript on $uu$ in $P$ was $k$, give all of these new copies of $uu$ the subscript $k+1$ (i.e. give them a subscript of 1 if $uu$ did not appear in $P$). This new multiset partition is $\varphi(P)$. Conversely, if $u$ is not repeated in any block of $P$ but $uu$ appears, assume $k$ is the largest subscript on $uu$ in $P$. Then split every instance of $uu_k$ into two copies of $u$. We define this to be $\varphi(P)$. This map $\varphi$ is an involution, and since it alters the number of subscripted even length words by one, it is sign-reversing, i.e. $\sgn(P)+\sgn(\varphi(P))=0$. \begin{ex} For the following $P, P' \in \MP_{(25,18), (2,1,1)}$, we have $u=112$, $\varphi(P)=P'$, and $\varphi(P')=P$. Notice that $\sgn(P)=(-1)^3=-1$ and $\sgn(P') = (-1)^4 =+1$, as desired. $$P = 1,112,112, 2,2 \mid 1,112,112,2,2 \mid 112,112112_1,22_1 \mid 112, 112, 112, 112, 12_1$$ $$P' = 1,112112_2,2,2 \mid 1,112112_2,2,2 \mid 112,112112_1,22_1 \mid 112112_2, 112112_2, 12_1$$ \end{ex} %\end{subsubsection} \medskip %\begin{subsubsection} \noindent{\bf Case 2: Even length Lyndon words repeated within blocks.} In this case, we assume that $P \in \MP_{\lambda, \gamma}$ does not fall in Case 1 and contains at least one block with a repeated even length Lyndon word (with any subscripts). Recall that $P \in \MP_{\lambda, \gamma}$ contains $\gamma_i$ identical blocks for each $i \leqslant \ell(\gamma)$. We refer to each multiset of identical blocks as a \emph{multiblock} and call the number of blocks within it its \emph{multiplicity}, $\gamma_i$. Let $\mathcal{B}= \{\!\!\{ B^{\gamma_i} \}\!\!\} $ denote a multiblock containing the block $B$ with multiplicity $\gamma_i$. Choose $w$ to be the lexicographically smallest even length Lyndon word in $P$ that is repeated within a block. We define the function $f_w$ which forgets the subscripts on all instances of the word $w$. Consider the subset $\mathcal{L}(P,w) \subseteq\MP_{\lambda, \gamma}$ defined as $\mathcal{L}(P,w) = \{P': f_w(P') = f_w(P)\}. $ We show that \begin{equation}\label{eqn: case 2 goal} \sum_{P' \in \mathcal{L}(P,w)} \sgn(P') = 0. \end{equation} A collection of multiblocks $\mathcal{B}_1, \dots, \mathcal{B}_k$ are \emph{$w$-distinguishable} if the subscripts on $w$ are what distinguish the blocks of these multiblocks. In other words, for all $i,j \leq k$, for each $B_i \in \mathcal{B}_i$ and $B_j \in \mathcal{B}_j$, $f_w(B_i) = f_w(B_j)$. For example, two multiblocks containing the blocks $\{1,2,12_1,13_1\}$ and $\{1,2,12_1,13_2\}$ are $13$-distinguishable but are not $12$-distinguishable. If no two multiblocks containing $w$ are $w$-distinguishable, we show Equation \ref{eqn: case 2 goal} via a bijection to tableaux and an application of Lemma \ref{h to m like cancellation}. This bijection requires ordering the multiblocks in which $w$ appears lexicographically. Example \ref{case 2 ex} is an example of this. Else, if some of the multiblocks containing $w$ are $w$-distinguishable, the proof of Equation \ref{eqn: case 2 goal} is more subtle, and Lemma \ref{diff rows lem} is needed. \begin{lem}\label{h to m like cancellation} Fix $\beta \in \Comp(n)$, the set of all compositions of $n$. Let $R^\geq_{\beta, \alpha}$ denote the number of tableaux of shape $\beta$ and content $\alpha \in \Comp(n)$ with rows weakly increasing (but with no restrictions on columns). Then \[\sum_{\alpha \in \Comp(n)} (-1)^{\ell(\alpha)} R^\geq_{\beta, \alpha} = \begin{cases} (-1)^n & \text{ if } \beta=(1^n) \\ 0 & \text{ else.} \end{cases}\] \end{lem} \begin{ex}\label{case 2 ex} Let $P = 1, 12_1 \mid 1,12_2,12_3,13_1$. Then $w=12$ and $\mathcal{L}(P,w)\subseteq \MP_{(6,3,1),(1,1)}$ contains the following eight elements, which are in bijection with composition fillings of the shape $(1,2)$, and whose signs sum to $0$: %\BA{I'm not sure what's causing it but there seems to be more space between the rows starting with $P_1$ and $P_2$ than between the other ones}\mike{fixed by putting a noindent. I also have no idea why that works. I just tried a half of a dozen things} \noindent \[\ytableausetup{boxsize=12pt} P_1=1, 12_1 \mid 1,12_2,12_3,13_1 \ \mapsto \ \begin{ytableau} 1 \\ 2 & 3 \\ \end{ytableau} \quad \quad P_5=1, 12_2 \mid 1,12_1,12_1,13_1 \ \mapsto \ \begin{ytableau} 2 \\ 1 & 1 \\ \end{ytableau} \] \[P_2=1, 12_2 \mid 1,12_1,12_3,13_1 \ \mapsto \ \begin{ytableau} 2 \\ 1 & 3 \\ \end{ytableau} \quad \quad P_6=1, 12_1 \mid 1,12_2,12_2,13_1 \ \mapsto \ \begin{ytableau} 1 \\ 2 & 2 \\ \end{ytableau} \] \[P_3=1, 12_3 \mid 1,12_1,12_2,13_1 \ \mapsto \ \begin{ytableau} 3 \\ 1 & 2 \\ \end{ytableau} \quad \quad P_7=1, 12_2 \mid 1,12_1,12_2,13_1 \ \mapsto \ \begin{ytableau} 2 \\ 1 & 2 \\ \end{ytableau} \] \[P_4=1, 12_1 \mid 1,12_1,12_2,13_1 \ \mapsto \ \begin{ytableau} 1 \\ 1 & 2 \\ \end{ytableau} \quad \quad P_8=1, 12_1 \mid 1,12_1,12_1,13_1 \ \mapsto \ \begin{ytableau} 1 \\ 1 & 1 \\ \end{ytableau} \] \end{ex} %\textcolor{red}{Can we add the tableau to which they map, on the same row very small?} \begin{lem}\label{diff rows lem} Fix $\beta \neq (1^n) \in \Comp(n)$. Let $\mathcal{C} = \{C_1, \dots, C_k\}$ be a set partition of $[\ell(\beta)]$ such that if $i,j \in C_m$, then $\beta_i = \beta_j$. Let $D_\mathcal{C}$ denote the set of tableaux $T$ of shape $\beta$ and any composition content such that rows are weakly increasing and for each $C_m \in \mathcal{C}$, the rows of $T$ indexed by the elements of $C_m$ are all different. Let $\alpha(T)$ denote the content composition of $T$, such that $\alpha_i$ is the number of $i$'s in $T$. Then \[ \sum_{T \in D_\mathcal{C}} (-1)^{\ell(\alpha(T))} = 0.\] \end{lem} %\end{subsubsection} %\begin{subsubsection} \noindent{\bf Case 3: Even length Lyndon words repeated across non-identical blocks.} Here, we assume that $P$ does not fall in Cases 1 or 2 and has at least one even length Lyndon word that appears (with any subscripts) in more than one multiblock. Two multiblocks are \emph{word equivalent} if their blocks are identical when we remove the subscripts from all even length Lyndon words within them. For example, two multiblocks containing the blocks $\{1,2,12_2,13_1\}$ and $\{1,2,12_1,13_2\}$ are word equivalent. We can partially order the set of multiblocks of $P \in \MP_{\lambda, \gamma}$ using lexicographic order (ignoring subscripts) on their blocks. For a choice of total order compatible with this partial order (i.e. where an order is chosen for the multiblocks within each word equivalent collection), we say that an even length word $w$ has the \emph{standard labeling} with respect to this total order if its subscript in the $i$th smallest multiblock in which it appears is $i$. We address the following subcases: \begin{enumerate} \item \textbf{$P$ contains at least one even length Lyndon word $w$ that is not contained in any word equivalent multiblocks and does not have the standard labeling.} Then similarly to Case 2, we choose the lexicographically smallest such $w$, and a bijection to tableaux and application of Lemma \ref{h to m like cancellation} shows that the signs of all elements of $\mathcal{L}(P,w)$ with nonstandard labelings sum to $0$. \item \textbf{$P$ does not satisfy subcase 1, and $P$ contains a collection of word equivalent multiblocks that have an even number of even length Lyndon words per block.} We let $E$ denote the set of all even length Lyndon words (without subscripts) that appear in at least one collection of word equivalent multiblocks in $P$. Let $f_E$ be the function that forgets subscripts on all words in $E$, and define $\mathcal{L}(P,E) = \{P' \in \MP_{\lambda, \gamma}: f_E(P)=f_E(P')\}$. Then a technical proof involving Lemma \ref{labels for distinct multiblocks} and a variant of Lemma \ref{h to m like cancellation} for tableaux with strictly increasing rows shows that $ \sum_{P' \in \mathcal{L}(P,E)} \sgn(P') = 0$. \end{enumerate} \begin{lem}\label{labels for distinct multiblocks} Let $\mathcal{X} =\{X_1, \dots, X_m\}$ be a set such that each $X_i$ is a set consisting of the same $k$ even length Lyndon words, but different $X_i$'s may have different subscripts on these words. For each word $w$ appearing in $\mathcal{X}$, for each $2 \leqslant j \leqslant m$, $w_j$ can only appear if $w_{j-1}$ also appears somewhere in $\mathcal{X}$. Define $\sgn(\mathcal{X})$ to be $(-1)^{e(\mathcal{X})}$ where $e(\mathcal{X})$ is the number of distinct subscripted words appearing in $\mathcal{X}$. Then the sum of the signs of the $\mathcal{X}$'s is \[\sum_{\mathcal{X} \text{ a set}} \sgn(\mathcal{X}) = \begin{cases} 0 & \text{if $k$ is even} \\ (-1)^{km} & \text{if $k$ is odd.} \end{cases}\] \end{lem} \begin{enumerate} \item[3.] \textbf{$P$ does not satisfy subcases 1 or 2, and $P$ contains a collection of word equivalent multiblocks that have an odd number of even length words per block, some of which do not have a standard labeling.} Then applying the same lemmas as in subcase 2, the signs of the elements of $\mathcal{L}(P,E)$ that do not have a standard labeling on all even length words sum to $0$. \end{enumerate} \begin{ex} The following elements of $\MP_{(7,3,3),(1,1,1)}$ fall in each of the subcases of Case 3. $P_1=1,12_1,13_2 \mid 1, 13_2, 2 \mid 12_2,13_1$ satisfies subcase 1, as $P_1$ has no word equivalent multiblocks and $13$ does not have the standard labeling. Next $P_2 = 1,12_1, 13_1 \mid 1,12_2, 13_2 \mid 1,2,3 $ satisfies subcase 2, as two multiblocks are word equivalent and have two even length words per block. Finally $P_3 = 1, 12_3 \mid 1, 12_1 \mid 12_2, 13_1, 133$ satisfies subcase 3, since the first two multiblocks are word equivalent and contain one even length word, $12$, which does not have a standard labeling, since to be standard, $12$ would need subscripts $1,2$ in the first two multiblocks and $3$ in the last. \end{ex} Thus the elements from Case 3 that we have not yet eliminated are those $P$ in which all even length words appearing in multiple multiblocks have a standard labeling and all collections of word equivalent multiblocks have an odd number of even length words per block. %\end{subsubsection} \medskip \noindent{\bf Case 4: All remaining elements of $\MP_{\lambda, \gamma}$.} The remaining elements in $\MP_{\lambda, \gamma}$ have only Lyndon word entries, no repeated words within a block, and a standard labeling on all even length words. In addition, two multiblocks can only be word equivalent if they contain an odd number of even length words per block. \begin{ex}\label{case 4 ex 1} Two elements that fall in Case 4 are the following $P_1 \in \MP_{(5,4,4), (3,2,2)}$ and $P_2 \in \MP_{(18,13,2), (2,2,1,1,1)}$: \[P_1 = 1 \mid 1 \mid 1\mid 13_1, 23_1\mid 13_1, 23_1 \mid 2 \mid 2\] \[P_2= 1,12_1 \mid 1,12_1 \mid 1, 12_2 \mid 1,12_3 \mid 1,12_3 \mid 1112_1, 12_4, 2, 23_1 \mid 1112_2, 12_5, 2, 23_2 \] \end{ex} Showing that the signs of these remaining elements sum to $0$ relies heavily on the next lemma. Its proof uses Kulikauskas and Remmel's combinatorial interpretation for the $M(m,e)$ transition matrix given in \cite[Theorem 2]{KR06}, applied to $m_{(1^n)}$. \begin{lem}\label{odd & even bij} Let $\alpha$ be a weak composition of size $>1$ and length $\ell$. Define \[\mathcal{W}_\alpha := \{W: W \text{ is a set of Lyndon words of content }\{\!\!\{ 1^{\alpha_1}, 2^{\alpha_2}, \dots, \ell^{\alpha_{\ell}}\}\!\!\}\},\] meaning, the number of $i$'s used in each $W$ is $\alpha_i$. Let $e(W)$ denote the number of even length words in $W$. Then \[ \sum_{W \in \mathcal{W}_\alpha} (-1)^{e(W)}= 0,\text{ and } |\{W \in \mathcal{W}_\alpha: e(W) \text{ is even}\}| = |\{W \in \mathcal{W}_\alpha: e(W) \text{ is odd}\}|.\] \end{lem} %\end{subsubsection} The \emph{content} of a block $B$ is the weak composition $\alpha$ such that the number of $i$'s in $B$ is $\alpha_i$ (i.e. the sum of the content vectors of the words in $B$). We say that two multiblocks are \emph{content equivalent} if they have the same content per block. If $P \in \MP_{\lambda, \gamma}$ has at least one multiblock that is not content equivalent to any other and has content of size $>1$ per block, then we show that the sign of $P$ cancels out by a direct application of Lemma \ref{odd & even bij}. See Example \ref{case 4(a)}. \begin{ex}\label{case 4(a)} The signs of the following four elements of $\MP_{(4,4),(2)}$ sum to $0$ by Lemma \ref{odd & even bij}: \[ P_1=1122_1\mid 1122_1 \quad \quad P_3=112,2 \mid 112,2\] \[P_2=1,122 \mid 1,122 \quad \quad P_4=1,12_1,2 \mid 1,12_1,2\] \end{ex} If every multiblock in $P$ is content equivalent to another multiblock in $P$, then to perform our final cancellations, we construct a sign-reversing involution using the bijection shown in Lemma \ref{odd & even bij} and taking into account that multiblocks with an odd number of even length words can repeat (if given a standard labeling on all even length words). This final subcase addresses the remaining elements of $\MP_{\lambda, \gamma}$ and completes the proof. \section{Applications of the main theorem} \label{sec: other transition matrices} \subsection{A change of basis from $\tilde{h}$ to the monomial basis}\label{subsec: ht to m} An expansion of the $\tilde{h}$ basis into the monomial basis is obtained by combining Theorem \ref{htil to h} and the combinatorial interpretation for the $M(h,m)_{\mu, \gamma}$ coefficient as the number of tableaux of content $\mu$ and shape $\gamma$ with rows weakly increasing, where the content of a tableau is the sum of the content vectors of the words in all the cells. The proof of Theorem \ref{htil to m} involves a simple application of Lemma \ref{h to m like cancellation} to make some cancellations. \begin{theorem}\label{htil to m} For partitions $\lambda, \gamma$ with $|\gamma| \leqslant |\lambda|$, $M(\tilde{h},m)_{\lambda, \gamma}$ is equal to $(-1)^{|\lambda|+|\gamma|}$ times the number of tableaux of content $\lambda$ and shape $\gamma$ whose entries are quasi-Lyndon words such that rows are lexicographically weakly increasing but only odd length words can repeat within a row. \end{theorem} \begin{ex}Suppose $\lambda = (3,2)$ and $\gamma = (2,1)$. Then $M(\tilde{h},m)_{\lambda, \gamma} = (-1)^{5+3} \cdot 12 = +12$ and is counted by the following tableaux: \begin{scriptsize} \ytableausetup{boxsize=15pt} \[\begin{ytableau} 1 & 1 \\ 122 \end{ytableau} \quad \begin{ytableau} 1 & 11 \\ 22 \end{ytableau} \quad \begin{ytableau} 1 & 112 \\ 2 \end{ytableau} \quad \begin{ytableau} 1 & 12 \\ 12 \end{ytableau} \quad \begin{ytableau} 1 & 122 \\ 1 \end{ytableau} \quad \begin{ytableau} 1 & 2 \\ 112 \end{ytableau} \quad \begin{ytableau} 1 & 22 \\ 11 \end{ytableau} \quad \begin{ytableau} 11 & 12 \\ 2 \end{ytableau} \quad \begin{ytableau} 11 & 2 \\ 12 \end{ytableau} \quad \begin{ytableau} 11 & 22 \\ 1 \end{ytableau}\quad \begin{ytableau} 112 & 2 \\ 1 \end{ytableau} \quad \begin{ytableau} 12 & 2 \\ 11 \end{ytableau} \]\end{scriptsize} \end{ex} \subsection{A change of basis from $\tilde{h}$ to Schur functions}\label{subsec: ht to s} An expansion of the $\tilde{h}$ basis into the Schur basis is obtained by combining Theorem \ref{htil to h} and the combinatorial interpretation for the $M(h,s)_{\mu, \gamma}$ coefficient, which is the Kostka number $K_{\gamma, \mu}$, the number of semistandard tableaux of content $\mu$ and shape $\gamma$. The following lemma concerning skew shape tableaux of composition content is used to perform cancellations in the proof of Theorem \ref{htil to s}. \begin{lem}\label{skew shp lem} Let $\nu \subseteq \lambda$ such that $\lambda / \nu$ is a skew shape with $|\lambda / \nu| = |\lambda| - |\nu|= n$. Denote by $\SSYT(\lambda / \nu, \alpha)$ the set of semistandard tableaux of shape $\lambda / \nu$ and content $\alpha \in \Comp(n)$. Then \[\sum_{\alpha \in \Comp(n)} \sum_{T \in \SSYT(\lambda / \nu, \alpha)} (-1)^{\ell(\alpha)} = \begin{cases} (-1)^n & \text{if $\lambda /\nu$ is a vertical strip,} \\ 0 & \text{else.} \end{cases}\] \end{lem} \begin{theorem}\label{htil to s} For partitions $\lambda,\gamma$ with $|\gamma|\leqslant|\lambda|$, $M(\tilde{h}, s)_{\lambda, \gamma}$ is equal to $(-1)^{|\lambda|+|\gamma|}$ times the number of tableaux of content $\lambda$ and shape $\gamma$ whose entries are quasi-Lyndon words, such that rows are weakly lexicographically increasing but only odd length words can repeat within a row, and columns are weakly lexicographically increasing but only even length words can repeat within a column. \end{theorem} \begin{ex} Suppose $\lambda = (4,2)$ and $\gamma=(2,1)$. Then $M(\tilde{h},s)_{\lambda, \gamma} = (-1)^{6+3} \cdot 11 = -11$ and is counted by the following tableaux: \ytableausetup{boxsize=17pt} \begin{scriptsize} \[\begin{ytableau} 1 & 1 \\ 1122 \end{ytableau} \quad \begin{ytableau} 1 & 11 \\ 122 \end{ytableau} \quad \begin{ytableau} 1 & 122 \\ 11 \end{ytableau} \quad \begin{ytableau} 1 & 12 \\ 112 \end{ytableau} \quad \begin{ytableau} 1 & 112 \\ 12 \end{ytableau} \quad \begin{ytableau} 11 & 22 \\ 11 \end{ytableau} \quad \begin{ytableau} 11 & 12 \\ 12 \end{ytableau} \quad \begin{ytableau} 11 & 112 \\ 2 \end{ytableau} \quad \begin{ytableau} 11 & 2 \\ 112 \end{ytableau}\quad \begin{ytableau} 1 & 2 \\ 1112 \end{ytableau} \quad \begin{ytableau} 1 & 1112 \\ 2 \end{ytableau} \]\end{scriptsize} \end{ex} \subsection{Transition matrices for the $\tilde{h}_{\lambda_1} \cdots \tilde{h}_{\lambda_\ell}$ basis}\label{subsec: prods} %BA: not sure if we want to include this last subsection As shown in \cite{OZProds}, the family $\{ \tilde{h}_{\lambda_1}\tilde{h}_{\lambda_2}\cdots \tilde{h}_{\lambda_{\ell(\lambda)}}\}_\lambda$ forms a multiplicative inhomogeneous basis for the ring of symmetric functions. The basis elements are the characters of tensor products of trivial symmetric group representations with a diagonal action of the group. The family will be represented by $\prod \tilde{h}$ as short notation representing the collection of symmetric functions. As the $\prod \tilde{h}$ basis is multiplicative, it can be shown that Theorem \ref{htil to h} implies the following interpretation for the expansion of the $\prod \tilde{h}$ basis into the $h$ basis. A positive rule for the coefficient of $\tilde{h}_\gamma$ in $\tilde{h}_{\lambda}\tilde{h}_{\mu}$ is explained in \cite{OZHopf} and the following combinatorial interpretations are developed by formulating an interpretation for the transition matrix $M(\prod \tilde{h}, h)$ and multiplying by $M(h,m)$ and $M(h,s)$, respectively for the two corollaries. %\BA{Just to clarify, I did not come up with an interpretation for $M(\prod \tilde{h}, \tilde{h})$ - not sure if the previous sentence is trying to say that this is how I proved these theorems, because this is not what I did (though I imagine it could be possible but perhaps more complicated). The rough sketch of the proof is at the end of the "ht to h,m,s" file, and I just expand each $\tilde{h}_{\lambda_i}$ into $h$'s and multiply essentially. But maybe I am misinterpreting the point of the previous sentence and you understood what I meant in my earlier comment, and in that case, you can disregard this whole comment!} \begin{theorem}\label{prod htil to h} For partitions $\lambda,\mu$ with $|\mu|\leqslant|\lambda|$, $M(\prod \tilde{h}, h)_{\lambda, \mu} = \sum_{S} \sgn(S)$ where the sum is taken over $S \in \mathcal{M}_{\lambda, \mu}$ (as defined for Theorem \ref{htil to h}) such that the only quasi-Lyndon words allowed in $S$ are of the form $a$ or $aa$ for some positive integer $a$. \end{theorem} Then interpretations for the expansions of the $\prod \tilde{h}$ basis into the $m$ and $s$ bases follow from Theorem \ref{prod htil to h} by proofs analogous to those of Theorems \ref{htil to m} and \ref{htil to s}. \begin{cor} For partitions $\lambda, \gamma$ with $|\gamma|\leqslant|\lambda|$, $M(\prod \tilde{h}, m)_{\lambda, \gamma}$ is equal to $(-1)^{|\lambda|+|\gamma|}$ times the number of tableaux of content $\lambda$ and shape $\gamma$ whose entries are words of the form $a$ or $aa$ for some positive integer $a$, such that rows are lexicographically weakly increasing but only words of length one can repeat within a row. \end{cor} \begin{cor} For partitions $\lambda,\gamma$ with $|\gamma|\leqslant|\lambda|$, $M(\prod \tilde{h}, s)_{\lambda, \gamma}$ is equal to $(-1)^{|\lambda|+|\gamma|}$ times the number of tableaux of content $\lambda$ and shape $\gamma$ whose entries are words of the form $a$ or $aa$ for some positive integer $a$, such that rows are lexicographically weakly increasing but only words of length one can repeat within a row, and columns are lexicographically weakly increasing but only words of length two can repeat within a column. \end{cor} %\acknowledgements{\BA{do we have any to add or can we remove this?}} %% if you use biblatex then this generates the bibliography %% if you use some other method then remove this and do it your own way \printbibliography \end{document}